Field
The described embodiments relate to techniques for revising connection strengths associated with edges between nodes in a social graph. More specifically, the described embodiments relate to techniques for revising the connection strengths based on user feedback.
Related Art
Social networks are an increasingly popular format for aggregating and interconnecting individuals who have similar interests. For example, a website may provide a professional social network for individuals in the workforce. These users may ‘connect’ with each other, thereby defining subsets of interrelated users in the social network. In principle, these interrelated users can facilitate a wide variety of value-added services, such as helping: the users find employment, employers recruit employees, educational institutions identify prospective students, etc. More generally, the interrelated users in a social network may facilitate targeted communication among the users.
In practice, these capabilities are typically implemented with a social graph that represents the interrelationships among the users of the social network. In particular, the social graph may include multiple nodes that are associated with the users or groups of users (such as businesses, educational institutions, clubs and, more generally, organizations) that are connected by edges. Moreover, a given edge between a pair of nodes may have an associated weight or connection strength. The connection strengths usually play an important role in analysis techniques that attempt to leverage the social graph to provide the value-added services. For example, when a user wishes to conduct business with a particular company, the cascading interrelationships specified by the connection strengths in the social graph (such as among the user and other users of the social network) may be used to identify friends of friends or indirect professional colleagues who may be good contact points in the company for the user to contact.
However, it is often difficult to accurately determine the connection strengths. For example, a provider of the social network often attempts to infer or estimate the connection strengths based on user activity in the social network (such as an average frequency of communication, a time since a last message between the users, etc.), user profiles (such as how long ago the users worked together or attended the same educational institution) and/or overlap between users' connections. Moreover, error or uncertainty in the estimated connection strengths often degrades the accuracy of analysis of the social graph, which cause a commensurate negative impact on the value-added services. For example, when trying to use the social graph to identify contact points in an organization, errors in the estimated connection strengths are compounded. Consequently, paths through the social graph that involve multiple edges and nodes (and, in particular, more than two or three degrees of separation from the user) may not provide useful information, which is often frustrating to the users.
Note that like reference numerals refer to corresponding parts throughout the drawings. Moreover, multiple instances of the same part are designated by a common prefix separated from an instance number by a dash.